{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5fe04205",
   "metadata": {},
   "source": [
    "# 数据结构学习"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "478ba20c",
   "metadata": {},
   "source": [
    "## 1 数组\n",
    "- 在连续空间中存储一系列相同类型的元素，通过索引下标直接访问\n",
    "- **特点：** 访问速度快O(n)，删除和插入效率低"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "4d88bd5e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5]\n",
      "[1, 2, 3, 4]\n",
      "[2, 3, 4]\n",
      "[2, 10, 3, 4]\n",
      "[2, 10, 10, 3, 4]\n",
      "[2, 10, 10, 10, 3, 4]\n",
      "[2, 10, 10, 3, 4]\n",
      "1\n",
      "2\n",
      "[2, 3, 4, 10, 10]\n",
      "[10, 10, 4, 3, 2]\n",
      "2\n",
      "[2, 3, 4, 10, 10]\n",
      "--------------------------------------------------\n",
      "[2, 5, 4, 10, 10]\n",
      "[2, 5, 4, 10, 10]\n",
      "--------------------------------------------------\n",
      "[2, 5, 4, 10, 10]\n",
      "[2, 10, 4, 10, 10]\n",
      "[]\n"
     ]
    }
   ],
   "source": [
    "# list\n",
    "a = [1, 2, 3, 4]\n",
    "# 动态数组\n",
    "# 1. 在末尾追加\n",
    "a.append(5)\n",
    "print(a)\n",
    "# 2. 在末尾弹出, 会范围弹出值\n",
    "it = a.pop()\n",
    "print(a)\n",
    "it2 = a.pop(0) # 弹出第一个元素，设置索引\n",
    "print(a)\n",
    "\n",
    "# 3. 插入 \n",
    "a.insert(1, 10)\n",
    "print(a)\n",
    "a.insert(2, 10)\n",
    "print(a)\n",
    "a.insert(2, 10)\n",
    "print(a)\n",
    "# 4. 删除\n",
    "a.remove(10) # 根据值来删除, 删除第一个元素\n",
    "print(a)\n",
    "# a.remove(10) # 根据 值 来删除\n",
    "# print(a)\n",
    "\n",
    "# 查找某一个值的索引\n",
    "it = a.index(10) # 第一个查找到的值就直接返回了\n",
    "print(it)\n",
    "\n",
    "it = a.index(10, 2)\n",
    "print(it)\n",
    "\n",
    "# 排序 默认是升序\n",
    "a.sort()\n",
    "print(a)\n",
    "\n",
    "a.sort(reverse=True) # 降序\n",
    "print(a)\n",
    "\n",
    "# 统计某一个元素出现的次数\n",
    "res = a.count(10)\n",
    "print(res)\n",
    "\n",
    "# 将列表倒转\n",
    "a.reverse()\n",
    "print(a)\n",
    "\n",
    "# 浅拷贝：\n",
    "b = a\n",
    "b[1] = 5\n",
    "print(\"-\"*50)\n",
    "print(b)\n",
    "print(a)\n",
    "# 深拷贝 \n",
    "b = a.copy()\n",
    "b[1] = 10\n",
    "print(\"-\"*50)\n",
    "print(a)\n",
    "print(b)\n",
    "\n",
    "# 清空列表\n",
    "a.clear()\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6e6d1b92",
   "metadata": {},
   "source": [
    "## 2 链表\n",
    "- 由一系列节点组成，每个节点包含数据和指向下一节点的指针，内存空间要求不连续\n",
    "- 插入和删除速度快O(n), 但是访问元素慢\n",
    "\n",
    "- 单向链表： 节点指向下一个节点\n",
    "- 双向链表： 节点指向前一个节点和后一个节点\n",
    "- 循环链表： 尾节点指向头节点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b4228ee6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-------\n"
     ]
    }
   ],
   "source": [
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "head = ListNode(1)\n",
    "# print(head)\n",
    "head.next = ListNode(2)\n",
    "\n",
    "head.next.next = ListNode(3)\n",
    "# if head.val < head.next.val:\n",
    "#     print(\"-------\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12720618",
   "metadata": {},
   "source": [
    "## 3 栈\n",
    "- 一种**后进先出**的集合，元素从一端（队尾）添加，从另一端（队首）移除\n",
    "- push入栈 和 pop 出栈"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "593834fb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "入栈 [1, 2, 3, 4, 5, 6, 7]\n",
      "出栈 [1, 2, 3, 4, 5, 6]\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "# 直接使用 list\n",
    "stack = [1, 2, 3, 4, 5, 6]\n",
    "# 入栈\n",
    "stack.append(7)\n",
    "print(\"入栈\", stack)\n",
    "\n",
    "# 出栈\n",
    "stack.pop()\n",
    "print(\"出栈\", stack)\n",
    "\n",
    "# 查看栈顶\n",
    "print(stack[-1])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a201187f",
   "metadata": {},
   "source": [
    "## 4 队列\n",
    "- 一种先进先出的集合。从队尾添加，从队首移除\n",
    "- 双端队列：两端都可以进行入队和出队操作\n",
    "- 优先队列：元素被赋予优先级，出队时按照优先级顺序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "68ed7837",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([1, 2, 3, 4, 5, 6])\n",
      "deque([1, 2, 3, 4, 5, 6, 7])\n",
      "deque([0, 1, 2, 3, 4, 5, 6, 7])\n",
      "deque([0, 1, 2, 3, 4, 5, 6])\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "deque([1, 2, 3, 4, 5, 6])"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 双端队列\n",
    "from collections import deque\n",
    "q = deque([1, 2, 3, 4, 5, 6])\n",
    "print(q)\n",
    "# 从右端入队\n",
    "q.append(7)\n",
    "print(q)\n",
    "\n",
    "# 从左端入队\n",
    "q.appendleft(0)\n",
    "print(q)\n",
    "\n",
    "# q[1] # 访问速度慢\n",
    "\n",
    "# 出队\n",
    "q.pop()\n",
    "print(q)\n",
    "q.popleft()\n",
    "q\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ee6ac25",
   "metadata": {},
   "source": [
    "## 5 树\n",
    "- 由n个节点组成的具有层次关系的集合。每个树节点有一个根节点，其余节点可以分为多个互不相交的子树\n",
    "- 根、父节点、子节点、叶子节点、深度、高度\n",
    "- 二叉树：每个节点最多两个子节点\n",
    "1. 满二叉树：每个节点要么有0个子节点，要么有2个子节点\n",
    "2. 完全二叉树：除了最后一层，其他层都被完全填满\n",
    "3. 二叉搜索树(BST)：左子树所有节点值 < 根节点值 < 右子树所有节点值\n",
    "4. 平衡二叉树(BBT)：任意节点的左右子树高度差不超过1\n",
    "- **堆**：一种特殊的完全二叉树。最大堆中的父节点的值总大于等于子节点，最小堆则相反"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "956f01ba",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 树节点\n",
    "class Node:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a45df65",
   "metadata": {},
   "source": [
    "## 6 图\n",
    "- 由顶点和连接顶点的边组成的集合。边可以有权重\n",
    "- 有向图\n",
    "- 无向图"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bcc8034b",
   "metadata": {},
   "source": [
    "## 7 哈希表\n",
    "- 通过哈希函数将键映射到数组中的一个位置来访问记录，以实现极快的查找速度\n",
    "- 插入、删除、查找的时间复杂度都是O(1)，但可能发生哈希冲突（不同的键映射到同一位置）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "be8a3c79",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'a': 1, 'b': 10, 'c': 6}\n",
      "{'b': 10, 'c': 6}\n",
      "{'b': 10}\n",
      "10\n",
      "{'b': 10, 'a': 11, 'd': 50}\n",
      "dict_items([('b', 10), ('a', 11), ('d', 50)])\n",
      "b 10\n",
      "a 11\n",
      "d 50\n"
     ]
    }
   ],
   "source": [
    "# Python中使用字典 \n",
    "# 默认是无序字典\n",
    "a =dict()\n",
    "a[\"a\"] = 1\n",
    "a[\"b\"] = 10\n",
    "a[\"c\"] = 6\n",
    "print(a)\n",
    "a.pop(\"a\") # 根据键值弹出\n",
    "print(a)\n",
    "\n",
    "a.popitem() # 默认弹出尾巴\n",
    "print(a)\n",
    "\n",
    "# 根据键查找值\n",
    "ans = a.get('b')\n",
    "print(ans)\n",
    "\n",
    "# 合并字典\n",
    "a.update({\"a\":11, \"d\": 50})\n",
    "print(a)\n",
    "\n",
    "# 返回一个可迭代列表\n",
    "print(a.items())\n",
    "for k, v in a.items():\n",
    "    print(k, v)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07dd5259",
   "metadata": {},
   "source": [
    "## 8 集合\n",
    "- 一个只有键没有值的字典，同样基于哈希表实现\n",
    "- 特点是元素无序，不重复，且必须是可哈希的"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bb3a3903",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 3}\n",
      "{1, 2, 3, 5}\n",
      "{1, 3, 5}\n",
      "{1, 3, 4, 5, 7}\n"
     ]
    }
   ],
   "source": [
    "# 集合\n",
    "a =set({1, 2, 3})\n",
    "print(a)\n",
    "a.add(5)\n",
    "print(a)\n",
    "a.remove(2)\n",
    "print(a)\n",
    "# 重复元素会自动合并\n",
    "a.update({4, 7, 5})\n",
    "print(a)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
